package com.chenxys.algorithm.leetcode;

import com.chenxys.algorithm.common.StringUtil;

import java.util.Stack;

/**
 * <p>
 *      <a href="https://leetcode.cn/problems/minimum-additions-to-make-valid-string/description/">构造有效字符串的最少插入数</a><br/>
 *      给你一个字符串word，你可以向其中任何位置插入"a"、"b"或"c"任意次，返回使word有效需要插入的最少字母数。[word 仅由字母 "a"、"b" 和 "c" 组成]<br/>
 * 　　  如果字符串可以由"abc"串联多次得到，则认为该字符串有效。<br/>
 *      例: <br/>
 *          输入：word = "b"<br/>
 *          输出：2<br/>
 *          解释：在 "b" 之前插入 "a" ，在 "b" 之后插入 "c" 可以得到有效字符串 "abc" 。<br/>
 *          <hr/>
 *          输入：word = "abc"<br/>
 *          输出：0<br/>
 *          解释：word 已经是有效字符串，不需要进行修改。<br/>
 * </p>
 *
 * @author Chenxys
 * @version V1.0
 * @Package com.chenxys.algorithm.leetcode
 * @date 2024/1/10 10:07
 * @Copyright ©
 */
public class LeetCode2645 {

    /**
     * <p>
     *     构造有效字符串的最少插入数
     * </p>
     * @param word 原字符
     * @return 最少次数
     */
    public static int addMinimum(String word) {
        int N = word.length();
        int[] d = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            d[i] = d[i - 1] + 2;
            if (i > 1 && word.charAt(i - 1) > word.charAt(i - 2))
                d[i] = d[i - 1] - 1;
        }
        return d[N];
    }

    /**
     * <p>
     *     构造有效字符串的最少插入数
     * </p>
     * @param word 原字符
     * @return 最少次数
     */
    public static int checkAddMinimum(String word) {
        int n = word.length();
        int res = word.charAt(0) - word.charAt(n - 1) + 2;
        for (int i = 1; i < n; i++) {
            res += (word.charAt(i) - word.charAt(i - 1) + 2) % 3;
        }
        return res;
    }


    public static void main(String[] args) {
        int maxLen = 100;
        int testTimes = 100000;
        System.out.println("Test Start!");
        for (int i = 0; i < testTimes; i++) {
            String lowerStr = StringUtil.generateRandomLowerStr(maxLen, 'a', 'c');
            if (addMinimum(lowerStr) != checkAddMinimum(lowerStr)) {
                System.out.println("Oops!");
                System.out.println(lowerStr);
                break;
            }
        }
        System.out.println("Test End!");
    }
}
